#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/4/26 18:20
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 169. 求众数.py
# @Software: PyCharm

"""  
169. 求众数
TODO模块说明
Public Class:
-	TODO类名: TODO类说明 
Public Methods: 
-	TODO方法名: TODO方法说明
"""


class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # nums.sort()
        # return nums[len(nums)//2]
        def work(a, idx):
            n = len(nums)
            if idx < 0 or idx >= n:
                return None
            l, r, h = 0, n-1, (n-1)//2
            while l < r:
                i, j, x = l, r, a[h]
                a[h] = a[i]
                while i<j:
                    while i<j and a[j]>=x:
                        j -= 1
                    if i<j:
                        a[i] = a[j]
                        i += 1
                    while i<j and a[i]<x:
                        i += 1
                    if i<j:
                        a[j] = a[i]
                        j -= 1
                a[i] = x
                if idx < i:
                    r = i-1
                elif idx > i:
                    l = i+1
                else:
                    return x
            print(l, idx)
            print(a[idx])
            if l == idx:
                print(True)
                return a[idx]
            else:
                return l
        return work(nums, len(nums)//2)



nums = [1]
solution = Solution()
print(solution.majorityElement(nums))
